This invention relates to searching in databases in order to find a match or partial match of address data in the database so as to retrieve associated data. The invention is primarily though not necessarily exclusively concerned with look-up databases employed in network units for use in a data communication system employing addressed frames or data packets.
It is necessary in data communication systems employing addressed frames or packets to perform look-ups in order to retrieve, directly or indirectly, for example by recourse to pointers, associated data such as forwarding data. A typical example is in a switch or router wherein while packets are temporarily stored, a look-up in an address database is performed in order to retrieve the forwarding data which will determine the port or ports from which any given packet should be forwarded from the switch or router. Look-up databases and techniques for operating them are very well established in the art.
In view of the potentially very great number of different destinations, whether expressed in media access control terms or network address terms, to which packets might have to be forwarded by a switch or router. A variety of techniques have been developed for reducing the amount of memory space which has to be employed in practice. Although directly searchable memories, usually called content addressable memories, are known, such memories are complex and expensive and are normally only used for relatively small capacity caches. Other techniques for reducing the amount of memory space required in practice include hashing, wherein addressed data is reduced (typically from 48 bits to 16 bits) by an appropriate hashing algorithm and the address data is stored in hashed form.
Such a scheme and other schemes such as the ones described below, typically require a final comparison of the full address associated with the hashed entry with the address of the packet requiring look-up in order to ensure that the correct entry is found.
An important technique for searching in look-up databases is a technique which employs a multi-way tree structure or trie search structure. Such structures are known in the art and are, for example, described in published European application EP-0551243-A (Digital Equipment Corporation), U.S. Pat. No. 6,041,053 (Douceur), an international published application WO96/00945 (IBM) and elsewhere. Trie searching has in common the establishment of a structure wherein a key is formed from all or part of the address data and is read in slices. At each stage of the search there is an entry which contains a pointer which points to a block of entries but does not distinguish between the entries in that block. Such a block is accessed at the next stage or slice of the search and that part of the key which is employed in that stare obtains the particular entry within the block. Each entry may include a status indication which indicates whether the search is finished or not or is successful or not.
Generally speaking, up to the present time a trie search facility has accommodated only a single search strategy, in which the order and sizes of the sections used in the search key are predetermined by the search engine externally of the trie structure. The aforementioned U.S. Pat. No. 6,041,053 employs what the patent calls xe2x80x98wild cardsxe2x80x99 to enable different search paths to a common node. The aforementioned European application EP-0551243-A describes a structure in which different search strategies may be determined in advance, allowing different root nodes to provide several traversal paths, each able to accommodate a different size and address format from among, the possible network addresses that can be input to the searching engine. Each database specifier will include information on the root node to be used for a particular network address.
However, such proposals are not adequate to cope conveniently with a possible change in search strategies. It is normal and convenient to optimise a trie search for a particular application or search strategy. For example, in a given switch a trie search mechanism may only be required for a layer 3 (network address) look-up. Accordingly, the trie key chosen for a trie search would be selected to be the most efficient for layer 3 look-ups. If a new xe2x80x98applicationxe2x80x99 or feature would now to require the use of the search engine, the key may not be optimised and in particular may slow down the search since the search would be using parts of the key that are relevant to the xe2x80x98layer 3xe2x80x99 application but not to the new application. As a particular example, a current search strategy may require a key composed of the IPDA (internet protocol or network destination address), an identification of the relevant virtual local area network (VLANID) and the IPSA (internet protocol or network source address). However, if the relevant device, for example a router, is employed for server load balancing, wherein a multiplicity of servers are in a server farm sharing the same virtual IPDA, a search made for the purpose of server load balancing, to obtain the forwarding, data required to direct a packet to the given server, may only require a search to be made for the IPSA, the network source address. However, with the fixed key the searching engine has to perform the trie search through the stages or sections of the IPDA and VLANID before it reaches the sections pertaining to the IPSA.
There exists therefore a need for a versatile and convenient manner of altering the search strategy in a trie search stricture, preferably in a manner which does not require any increase in memory, additional hardware or external programming.
The present invention is based on a novel data structure for the trie search which enables a selection of the next statue in a trie search to be determined by a given entry in the trie structure. In a preferred form, the invention contemplates the provision of at least an additional field for each entry in the database. This extra field, termed herein a xe2x80x98search codexe2x80x99 indicates to the search engine which section of a key should be used for the next search access. The search code is intended to indicate or delimit a section in the key that should be used to perform the next stare of the trie search. Accordingly, the trie sections actually employed in the search are selected from a basic key by means of the entries in the database. In effect the selection of the trie key may be programmed into the database.